package oj;

/**
 * @author 郝文雪
 * @date 2022/7/16 17:16
 * @Description 寻找重复数
 */
public class LC287 {
    /**
     * 快慢指针，不需要额外空间
     * [1,3,4,2,2]建立如下映射关系：0-1  1-3 2-4 3-2 4-2
     * @param nums
     * @return
     */
    public int findDuplicate(int[] nums) {
        int slow=0;
        int fast=0;
        slow=nums[slow];
        fast=nums[nums[fast]];
        while(slow!=fast){
            slow=nums[slow];
            fast=nums[nums[fast]];
        }
        int pre1=0;
        int pre2=slow;
        while(pre1!=pre2){
            pre1=nums[pre1];
            pre2=nums[pre2];
        }
        return pre1;
    }

    /**
     * 需要额外空间，不需要修改原数组的计数法
     * @param nums
     * @return
     */
//    public int findDuplicate(int[] nums) {
//        int[] arr=new int[nums.length+1];
//        for(int i=0;i<nums.length;i++){
//            arr[nums[i]]++;
//            if(arr[nums[i]]>1) return nums[i];
//        }
//
//        return nums.length;
//    }
}
